/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

#define hash_lock()		emutex_lock(&hash->mutex)
#define hash_unlock()		emutex_unlock(&hash->mutex)

/*
 * Prototypes
 */
static inline eint32_t
key_hash(eint8_t *vector, eint32_t key, eint32_t length);

static eint32_t
mpz_hash(empz_t z);

static inline eint32_t
mpq_hash(empq_t z);

static eint32_t
mpr_hash(empr_t z);

static inline eint32_t
cqq_hash(ecqq_t qq);

static inline eint32_t
mpc_hash(empc_t rr);

static eint32_t
hashentry_key(ehashentry_t *entry);

static inline ebool_t
mpr_compare(empr_t a, empr_t b);

static ebool_t
hashentry_compare(ehashentry_t *left, ehashentry_t *right);

static void
rehashtable(ehashtable_t *hash);

static void
builtin_hash(eint32_t count);

/*
 * Implementation
 */
void
init_hashtable(void)
{
    esymbol_t	*symbol;

    symbol = enew_symbol(ht_language, eget_string((euint8_t *)"hash", 4));
    edefine_builtin(enew_bound_symbol(symbol), builtin_hash, 0, false);
}

void
enew_hashtable(eobject_t *pointer, eint32_t size)
{
    eint32_t		 i;
    ehashtable_t	*hash;

    /* limit initial size to 1 << 16 */
    if (size <= 0)
	size = 16;
    else if (size > (1 << 16))
	size = 1 << 16;
    else if (size & (size - 1)) {
	for (i = 1 << 15; i >= 0; i >>= 1)
	    if (size & i)
		break;
	size = i << 1;
    }

    enew_object(pointer, t_hashtable, sizeof(ehashtable_t));
    hash = *(ehashtable_t **)pointer;
    enew_object((eobject_t*)&hash->entries,
		t_resize | t_void, size * sizeof(ehashentry_t*));
    hash->size = size;
    emutex_init(&hash->mutex);
}

void
ekey_hashentry(ehashentry_t *entry)
{
    entry->key = hashentry_key(entry);
}

void
eput_hashentry(ehashtable_t *hash, ehashentry_t *entry)
{
    eint32_t		 key;
    ehashentry_t	*prev, *ptr;

    hash_lock();
    key = entry->key & (hash->size - 1);
    prev = ptr = hash->entries[key];
    for (; ptr; prev = ptr, ptr = ptr->next) {
	if (hashentry_compare(entry, ptr)) {
	    /* replace existing entry */
	    if (ptr == prev)
		hash->entries[key] = entry;
	    else
		prev->next = entry;
	    entry->next = ptr->next;
	    hash_unlock();
	    return;
	}
    }

    /* add new entry */
    if (prev)
	prev->next = entry;
    else
	hash->entries[key] = entry;

    ++hash->count;

    if (hash->count > (hash->size >> 1) + (hash->size >> 2))
	rehashtable(hash);
    hash_unlock();
}

ehashentry_t *
eget_hashentry(ehashtable_t *hash, ehashentry_t *entry)
{
    eint32_t		 key;
    ehashentry_t	*ptr;

    hash_lock();
    key = entry->key & (hash->size - 1);
    for (ptr = hash->entries[key]; ptr; ptr = ptr->next)
	if (hashentry_compare(entry, ptr)) {
	    hash_unlock();
	    return (ptr);
	}

    hash_unlock();
    return (null);
}

void
erem_hashentry(ehashtable_t *hash, ehashentry_t *entry)
{
    eint32_t		 key;
    ehashentry_t	*ptr, *prev;

    hash_lock();
    key = entry->key & (hash->size - 1);
    for (ptr = prev = hash->entries[key]; ptr; prev = ptr, ptr = ptr->next) {
	if (ptr == entry) {
	    --hash->count;
	    if (ptr == prev)
		hash->entries[key] = ptr->next;
	    else
		prev->next = ptr->next;
	    break;
	}
    }
    hash_unlock();
}

static inline eint32_t
key_hash(eint8_t *vector, eint32_t key, eint32_t length)
{
    eint32_t	 i;
    eint8_t	*ptr;

    for (i = 0, ptr = vector; i < length; i++)
	key = (key << (key & 1)) ^ ptr[i];

    return (key & 0x7fffffff);
}

static eint32_t
mpz_hash(empz_t z)
{
    eint32_t	key;
    eint32_t	length;

    if (z->_mp_size < 0) {
	key = -1;
	length = -z->_mp_size;
    }
    else {
	key = 0;
	length = z->_mp_size;
    }

    return (key_hash((eint8_t *)z->_mp_d, key, length >> 3));
}

static inline eint32_t
mpq_hash(empq_t q)
{
    return (mpz_hash(mpq_numref(q)) ^ mpz_hash(mpq_denref(q)));
}

static eint32_t
mpr_hash(empr_t r)
{
    eint32_t	key;

    if (!mpfr_number_p(r) || mpfr_zero_p(r))	return (0);
    if (r->_mpfr_sign < 0)			key = -1;
    else					key = 0;

    key = key_hash((eint8_t *)r->_mpfr_d, key, (r->_mpfr_prec - 1) >> 3);

    return ((key ^ r->_mpfr_exp) & 0x7fffffff);
}

static inline eint32_t
cqq_hash(ecqq_t qq)
{
    return (mpq_hash(cqq_realref(qq)) ^ mpq_hash(cqq_imagref(qq)));
}

static inline eint32_t
mpc_hash(empc_t rr)
{
    return (mpr_hash(mpc_realref(rr)) ^ mpr_hash(mpc_imagref(rr)));
}

static eint32_t
hashentry_key(ehashentry_t *entry)
{
    switch (entry->nt & ~t_const) {
	case t_int:
	case t_float:
	    return (key_hash((eint8_t *)&entry->nv.i, 0, sizeof(eint_t)));
	case t_mpz:
	    return (mpz_hash(entry->nv.z));
	case t_mpq:
	    return (mpq_hash(entry->nv.q));
	case t_mpr:
	    return (mpr_hash(entry->nv.r));
	case t_cdd:
	    return (key_hash((eint8_t *)&entry->nv.dd, 0, sizeof(ecdd_t)));
	case t_cqq:
	    return (cqq_hash(entry->nv.qq));
	case t_mpc:
	    return (mpc_hash(entry->nv.c));
	case t_string:
	    return (key_hash(entry->nv.v->v.i8, 0, entry->nv.v->length));
	default:
	    return (key_hash((eint8_t *)&entry->nv.o, 0, sizeof(eobject_t)));
    }
}

static inline ebool_t
mpr_compare(empr_t a, empr_t b)
{
    if (mpfr_signbit(a) == mpfr_signbit(b)) {
	if (likely(mpfr_number_p(a))) {
	    if (likely(mpfr_number_p(b)))
		return (mpfr_lessgreater_p(a, b) == 0);
	    return (false);
	}
	if (likely(!mpfr_number_p(b))) {
	    if (mpfr_nan_p(a))
		return (mpfr_nan_p(b));
	    return (mpfr_inf_p(b));
	}
    }
    return (false);	
}

static ebool_t
hashentry_compare(ehashentry_t *l, ehashentry_t *r)
{
    if ((l->nt & ~t_const) != (r->nt & ~t_const))
	return (false);
    switch (l->nt & ~t_const) {
	case t_int:
	    return (l->nv.i == r->nv.i);
	case t_float:
	    return (l->nv.i == r->nv.i);
	case t_mpz:
	    return (mpz_cmp(l->nv.z, r->nv.z) == 0);
	case t_mpq:
	    return (mpq_cmp(l->nv.q, r->nv.q) == 0);
	case t_mpr:
	    return (mpr_compare(l->nv.r, r->nv.r));
	case t_cdd:
	    return (l->nv.ii.re == r->nv.ii.re && l->nv.ii.im == r->nv.ii.im);
	case t_cqq:
	    return (mpq_cmp(cqq_realref(l->nv.qq), cqq_realref(r->nv.qq)) == 0 &&
		    mpq_cmp(cqq_imagref(l->nv.qq), cqq_imagref(r->nv.qq)) == 0);
	case t_mpc:
	    return (mpr_compare(mpc_realref(l->nv.c), mpc_realref(r->nv.c)) &&
		    mpr_compare(mpc_imagref(l->nv.c), mpc_imagref(r->nv.c)));
	case t_string:
	    return (l->nv.v->length == r->nv.v->length &&
		    memcmp(l->nv.v->v.obj, r->nv.v->v.obj, l->nv.v->length) == 0);
	default:
	    return (l->nv.o == r->nv.o);
    }
}

static void
rehashtable(ehashtable_t *hash)
{
    eint32_t		 i, key, size;
    ehashentry_t	*entry, *next, **entries;

    if ((size = hash->size << 1) < 0)
	return;

    /* ensure all entries are reachable */
    enew_vector(&hash->vector, t_void, hash->count + 1, 1);
    entries = (ehashentry_t **)hash->vector->v.obj;
    for (i = key = 0; i < hash->size; i++)
	for (entry = hash->entries[i]; entry; entry = entry->next)
	    /* reserve first slot */
	    entries[++key] = entry;

    /* rehash */
    enew_object((eobject_t *)entries, t_void, size * sizeof(ehashentry_t *));
    /* also keep new entries vector reachable */
    entries = *(ehashentry_t ***)entries;
    for (i = 0; i < hash->size; i++) {
	for (entry = hash->entries[i]; entry; entry = next) {
	    next = entry->next;
	    key = entry->key & (size - 1);
	    entry->next = entries[key];
	    entries[key] = entry;
	}
    }

    /* update hash table */
    hash->entries = entries;
    hash->size = size;

    /* gc protected vector no longer required */
    hash->vector = null;
}

static void
builtin_hash(eint32_t count)
{
    enew_hashtable(&thread_self->obj, 0);
    thread_self->ret.v.o = thread_self->obj;
    thread_self->ret.t = t_hashtable;
}
